package lc;

public class Ex1095 {
    // class Solution {
    //     public int findInMountainArray(int target, MountainArray mountainArr) {
    //         int len = mountainArr.length(), res = -1;
    //         if (mountainArr.get(0) == target) return 0;
    //         // if (mountainArr.get(len - 1) == target)  {
    //         //     res = len - 1;
    //         // }
    
    //         //1.查找山顶
    //         //2.查找[left, 山顶]
    //         //3.查找[山顶,right)
    
    //         //根据与邻居相邻位置比较，决定是往左移动还是向右移动
    //         int lo = 1, hi = len - 2, top = -1, mid, m;
    //         while (lo <= hi) {
    //             mid = (hi - lo) / 2 + lo;
    //             m = mountainArr.get(mid);
    //             if (m > mountainArr.get(mid - 1) && m < mountainArr.get(mid + 1)) {
    //                 top = mid;
    //                 break;
    //             } else if (m < mountainArr.get(mid + 1)) {
    //                 lo = mid + 1;
    //             } else {
    //                 hi = mid - 1;
    //             }
    //         }
    //         //先查找[0, top]
    //         lo = 1;
    //         hi = top;
    //         while (lo < hi) {
    //              mid = (hi - lo) / 2 + lo;
    //             // if (mountainArr.get(mid) == target) {
    //             //     return mid;
    //             // } else if (mountainArr.get(mid) < target) {
    //             //     lo = mid + 1;
    //             // } else {
    //             //     hi = mid - 1;
    //             // }
    //             if (mountainArr.get(mid) > target) {
    //                 hi = mid - 1;
    //             } else {
    //                 lo = mid;
    //             }
    //         }
    //         if (mountainArr.get(lo) == target) return lo;
            
    //         lo = top + 1;
    //         hi = len - 1;
    //         while (lo <= hi) {
    //             mid = (hi - lo) / 2 + lo;
    //             if (mountainArr.get(mid) == target) {
    //                 return mid;
    //             } else if (mountainArr.get(mid) < target) {
    //                 lo = mid + 1;
    //             } else {
    //                 hi = mid - 1;
    //             } 
    //         }
    
    //         return -1;
    
    //     }
    
    //     public int binaryFind(int lo, int hi, MountainArray mountainArr, int target) {
    //         while (lo <= hi) {
    //             int mid = (hi - lo) / 2 + lo;
    //             if (mountainArr.get(mid) == target) {
    //                 return mid;
    //             } else if (mountainArr.get(mid) < target) {
    //                 lo = mid + 1;
    //             } else {
    //                 hi = mid - 1;
    //             }
    //         }
    //         return -1;
    //     }
    // }
}
